package inl.resilienceManager.qmul.gemom;


import java.util.*;

import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.TreeNode;

import resilienceManager.qmul.gemom.Gbroker;
import resilienceManager.qmul.gemom.NSitem;
import resilienceManager.qmul.gemom.bidNode;




/**
 * Main Auction class used for the bid
 * 
 * build the bid tree
 * 
 * search the bid tree 
 * 
 * COPYRIGHT DISCLAIMER
 * Synopsis: All the source codes presented in this document are intellectual
 * properties of Queen Mary, University of London.
 * 
 * @year 2010
 * @author Peng Jiang, John Bigham, Jiayi Wu Jinfu Wang------------QMUL
 * @version 1.0 
 */

public class AuctionTree {

	// the list of the items passed to tree
	private static NSitem[] itemlist ;

	// the list of the bidders
	private static Gbroker[] bidders;

	// the ID of Broken gbroker
	private int bgID;

	// the value list of the items
	private int[] valuelist;

	// the default root of the bid tree
	bidNode rootNode=null;
	
	
	// the vector for saving the leaf of the tree
//	private static Vector<bidNode> leafList = new Vector<bidNode>();
	private  Vector<bidNode> leafList = new Vector<bidNode>();
	
	// the risk value for the path
//	private static Vector<Double> riskList = new Vector<Double>();
	private Vector<Double> riskList = new Vector<Double>();
	
	// the linkedlist build by all the items;
//	private LinkedList<Integer> AllItems;
	private static LinkedList<Integer> AllItems;
	
	
	// the minimum risk for the search
	public double risk_sl;
	
	HashMap<String, String> nsmean = new HashMap<String, String>();

	/**
	 * constractor with the itemlist and gbroker list
	 * 
	 * gbroker list has the current 
	 * 
	 * */

	public AuctionTree(NSitem[] ilist, Gbroker[] glist, int id)
	{

//FIXME when search mirror allocation, a list of dead items used in search, a list of total items used in risk/variance matrix
		this.itemlist=ilist;

		this.bidders=glist;
// bgID? the bid tree's id?
		this.bgID = id;

		this.valuelist=new int[this.itemlist.length];

		for(int i=0; i< itemlist.length;i++)
		{
			this.valuelist[i]=itemlist[i].nslist.size();

		}
		
		AllItems = new LinkedList<Integer>();
		
		for(int i=0; i< itemlist.length;i++)
		{
			this.valuelist[i]=itemlist[i].nslist.size();
			AllItems.add(i+1);

		}
		
	}



	/**
	 * The main method to find all the sub set based on the linkedlist A
	 * 
	 * recursive algorithm
	 * */

	public static LinkedList<LinkedList<Integer>>  powSet(LinkedList<Integer> A)
	{	
		LinkedList<LinkedList<Integer>> ans= new LinkedList<LinkedList<Integer>> ();	
		if(A.size() == 1){//if there's only one element, we know the answer	

			ans.add(new LinkedList<Integer>());//empty set		

			LinkedList<Integer> temp= new LinkedList<Integer>();		

			temp.add(A.get(0));//and the only element in the original set	

			ans.add(temp);	

		}else{

			int first= A.remove(0);//save the first element		

			LinkedList<LinkedList<Integer>> partial= powSet(A);//recursion call		

			for(LinkedList<Integer> subset: partial) //for each set in the partial set
			{			
				//add it to the answer
				ans.add(subset);

				LinkedList<Integer> temp= new LinkedList<Integer>(subset);			
				//add the saved element to it	
				temp.add(first);
				//sort that set	
				Collections.sort(temp);	
				//add the new set to the answer
				ans.add(temp);		
			}	
		}	
		return ans;
	}



	/**
	 * according to the item list and gbroker list,build the bider tree 
	 * 
	 * */

	public void buildTree()
	{
		LinkedList<Integer> va=new LinkedList<Integer>(); 
//		FIXME if item set to allocace is null, getNull solution
		if(itemlist.length==0){
			
			return;
		}
		
		for(int i=0; i<itemlist.length; i++)
		{
			va.add((Integer)itemlist[i].getID());
		}

//		XXX !!!(generated itemset from va(all item no. Integer)) item no. in va start from 0; which is same as database
		LinkedList<LinkedList<Integer>> AllSet= powSet(va);

		//Allprint(AllSet);

		rootNode= new bidNode("Bid");



		for(int i=0; i<AllSet.size(); i++)
		{
			System.out.println("in 1st loop "+ i + " in " +AllSet.size());
			// FIXME the null bid is supposed to be bidded by bidders[0]
			Gbroker currentBid=bidders[0];
			
//one combination of items
			LinkedList<Integer> ta=AllSet.get(i);
			
//			if(ta.size()>0)
			if(true)
			{
//FIXME the acceptAll only consider bidded items not current on brokers				
				if(currentBid.acceptAll(getValueOflist(ta)))
				{
					String name="";
					for(int j=0; j<ta.size(); j++)
					{
//					XXX	the item id is +1 here, the item id in solution and bidnode start from 1
						int id=ta.get(j)+1;
						if(j!=(ta.size()-1))
							name=name+id+"-";
						else
							name=name+id;
					}
// build newNode 
					bidNode newNode= new bidNode(name,ta, currentBid);

					rootNode.add(newNode);
					
					LinkedList<Integer> tall=getItemAbove(newNode);

					LinkedList<LinkedList<Integer>> newSet=findPoSet(AllSet, tall);				

					buildNode(newNode, newSet, 1);
				}

			}
			else{
				System.out.println("ta.size()="+ta.size()+" and ta="+ta);
			}
		}

	}


	private  void buildNode(bidNode current,LinkedList<LinkedList<Integer>> PoSet, int GID )
	{
// FIXME and also stop the building the branch when all items are allocated
		// if reach the last bidder 
		if(GID> (bidders.length-1))
		{
//			System.out.println("reach leaf " + current);

			
			leafList.add(current);
			
			riskList.add(getRiskvalue(current));
			
			return;
		}
		
		if(PoSet.size()==1&& GID< (bidders.length)){
//			only dummy item
			bidNode newNode= new bidNode("", new LinkedList<Integer>(), bidders[GID]);
			current.add(newNode);
			buildNode(newNode, PoSet, GID+1);
//			TODO remove return will make no difference?
			return;
		}

		Gbroker currentBid=bidders[GID];

		for(int i=0; i< PoSet.size(); i++)
		{
			LinkedList<Integer> ta=PoSet.get(i);

//			if(ta.size()>0)
				if(true)
			{
				if(currentBid.acceptAll(getValueOflist(ta)))
				{
					String name="";
					for(int j=0; j<ta.size(); j++)
					{
						int id=ta.get(j)+1;
						if(j!=(ta.size()-1))
							name=name+id+"-";
						else
							name=name+id;
					}

					bidNode newNode= new bidNode(name,ta, currentBid);

					current.add(newNode);
					
					LinkedList<Integer> tall=getItemAbove(newNode);
				
	
					LinkedList<LinkedList<Integer>> newSet=findPoSet(PoSet, tall);
					// FIXME *no need* if ta is dummy bid - rmove the dummy bid in current PoSet! 
					buildNode(newNode,newSet, GID+1);
				}
			}

		}
/* if ta=null
		if list is empty (only the [] dummy) then it is leaf
		
		
*/		

	}


	private static LinkedList<LinkedList<Integer>> findPoSet(LinkedList<LinkedList<Integer>> PoSet, LinkedList<Integer> used)
	{
		if (used.size()==0){
//			leave dummy item
			return (LinkedList<LinkedList<Integer>>) PoSet.clone();
		}
		else{
			LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) PoSet.clone();


			for(int i=0; i< used.size(); i++){

				int itemID=used.get(i);
				tem=exceptItem(tem, itemID);

			}

			return tem;
		}
	}


	private static LinkedList<LinkedList<Integer>> exceptItem( LinkedList<LinkedList<Integer>> AL, int itemID)
	{

		LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) AL.clone();
		LinkedList<LinkedList<Integer>> deID=new LinkedList<LinkedList<Integer>>();


			for(int i=0; i<tem.size(); i++)
			{
				LinkedList<Integer> temList=tem.get(i);

				if(temList.contains((Integer)itemID))
				{
					deID.add(temList);
				}
			}
			
			tem.removeAll(deID);
		

		return tem;
		

	}

	private void Allprint( LinkedList<LinkedList<Integer>> AL)
	{
		for(int i=0; i<AL.size(); i++)
		{
			System.out.print("Set("+i+")=[");
			for(int j=0; j<AL.get(i).size(); j++)
			{
				System.out.print(AL.get(i).get(j)+",");
			}
			System.out.println("]");
		}
	}


	private static int getValueOflist(LinkedList<Integer> la)
	{
		int value=0;


		for(int i=0; i<la.size(); i++)
		{
//			itemlist is the items to bid
//			itemlist is not numbered by item id (0-n)
//			
			for (NSitem ni : itemlist){
//				the item(s) in la
				if (ni.getID()==la.get(i)){
//					itemset only has the items to bid
//					value=value+itemlist[la.get(i)].nslist.size();
					value=value+ni.nslist.size();
					break;
				}
//				else {
//					System.out.println(la.get(i)+" the item not in itemlist ");
//				}
			}
		}

		return value;

	}
	private static int getValueOflist2(LinkedList<Integer> la, NSitem[] items)
	{
//		items is the items to bid for
		int value=0;
		
		
		for(int i=0; i<la.size(); i++)
		{
//			itemlist is the items to bid
			value=value+items[la.get(i)].nslist.size();
		}
		
		return value;
		
	}


	/**
	 * find already used list
	 * 
	 * return already used the item list
	 * */
	private static LinkedList<Integer> getItemAbove(bidNode current)
	{
		LinkedList<Integer> above = (LinkedList<Integer>) current.getBidItem().clone() ;

		bidNode currentNode=current;
		
		while(!currentNode.toString().equals("Bid"))
		{
				bidNode pNode=(bidNode) currentNode.getParent();
//if item_.size()==0 skip
				if(!pNode.toString().equals("Bid"))
				{
					for(int i=0; i<pNode.getBidItem().size(); i++)
					{
						if(!above.contains(pNode.getBidItem().get(i)))
							above.add(pNode.getBidItem().get(i));
					}
					currentNode=pNode;
				}
				else
					return above;

		}

		return above;
	}


	


	// search the optimal path for the bid tree

	public DefaultMutableTreeNode SearchTree(){
		
		DefaultMutableTreeNode root= new DefaultMutableTreeNode("Bid");
		
		DefaultMutableTreeNode current = null;
		double minRisk=1000000;
		
		int bidID=0;
		for(int i=0; i< riskList.size(); i++)
		{
			double t=riskList.get(i);
			if((t>0)&&(t<minRisk))
			{
				minRisk=t;
				bidID=i;
			}
		}
		
		this.risk_sl=minRisk;
		//System.out.println("Normal Risk="+minRisk);
		bidNode winBid=leafList.get(bidID);
		
		TreeNode[] nodelist=winBid.getPath();
		
		//System.out.println("Length="+nodelist.length);
		
		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("Bid"))
			{
				// do nothing
				current=root;
				continue;
			}
			else
			{
				//bidNode temp=(bidNode) nodelist[i];
				
				DefaultMutableTreeNode addNode= new DefaultMutableTreeNode(nodelist[i].toString());
				current.add(addNode);
				
				current=addNode;
				
			}
		}
		
		return root;
			
	}
	
	
	// get the risk value for the bid node
	
	// return -1 mean not all the items include in the path
	
	// return >0 mean all the items are include in the path and this is the risk value for this path
	
	private static double getRiskvalue(bidNode leaf)
	{
		double risk = 0;
		
		Vector<Integer> totalItem=new Vector<Integer>();
		
		TreeNode[] nodelist=leaf.getPath();
		
		
		
		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("Bid"))
			{
				// nothing doing
				continue;
			}
			else
			{
				bidNode temp=(bidNode) nodelist[i];
				
				for(int j=0; j<temp.getBidItem().size();j++)
				{
//					total items in temp
					totalItem.add(temp.getBidItem().get(j));
				}
				
//				TODO !no need to change. itemlist is bidded items(not including bidder's current items) now both current and bid items are used 
				/*				if(temp.getBidderItemIDs()!=null && temp.getBidderItemIDs().size()>0){
									for(int j=0; j<temp.getBidderItemIDs().size();j++)
									{
										totalItem.add(temp.getBidderItemIDs().get(j));
									}			
								}*/
								
				
//				risk=risk+ bidders[i-1].getRisk(temp.getNodeVariance(itemlist),temp.getNodevalue(itemlist));
//				risk=risk+ temp.getBidder().getRisk(temp.getNodeVariance(itemlist),temp.getNodevalue(itemlist));
				risk=risk+ temp.getBidder().getRisk(temp.getNodeVariance(itemlist),temp.getNodeMean(itemlist));
				
			}
		}
		
		
		if(checkTotalItem(totalItem))
		{
			return risk;
		}
		else
		{
			risk=-1;
			return risk;
		}
		
	}
	
	
	private static boolean checkTotalItem(Vector<Integer> list)
	{
		boolean allincludes=false;
		
		if(list.size()!=itemlist.length)
			return allincludes;
		
		
		for(int i=0; i<list.size(); i++)
		{
			for(int j=i+1; j< list.size(); j++)
				if(list.get(i)==list.get(j))
					return allincludes;
		}
		
		return true;
	}



	public DefaultMutableTreeNode getBidTree()
	{
	
		return (DefaultMutableTreeNode)rootNode;
	}



}
